package 剑指Offer._2130;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/26 9:07
 * 链表中倒数第 k 个节点
 * 算法：链表  双指针
 * 先计算链表长度 n
 * 再将指针指向第 n - k 位置的节点
 * ---------------------------
 * 快慢指针
 * 先让快指针走 k 步
 * 再让慢指针走，当快指针走完时，慢指针的位置就是答案
 */
public class _22 {

    public ListNode getKthFromEnd(ListNode head, int k) {
        int len = 0;
        ListNode cur = head;
        while (null != cur) {
            ++len;
            cur = cur.next;
        }
        int res = len - k;
        if (res < 0) return null;
        if (res == 0) return head;
        cur = head;
        for (int i = 1; i <= res; i++) cur = cur.next;
        return cur;
    }

    public ListNode getKthFromEnd_doublePoints(ListNode head, int k) {
        ListNode slow = head, fast = head;
        for (int i = 1; i <= k; i++) fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

}
